"""
给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），
返回其最大和。

子数组 是数组中的一个连续部分。
"""
class Solution(object):
    #* Kadane's Algorithm
    def maxSubArray(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        n = len(nums)
        max_here = nums[0]
        max_sum = nums[0]
        
        for i in range(1, n):
            max_here += nums[i]
            if max_here <= nums[i]:  # 这个必须在前！
                max_here = nums[i]
            if max_here > max_sum:  # 顺序！！！
                max_sum = max_here
        
        return max_sum
